#include "common.h"

void quickSort(int array[], int n);
void quickSort0(int array[], int low, int high);
int partition(int array[], int low, int high);

void main()
{
    int array[] = {6, 5, 4, 3, 2, 1};
    int len = 6;
    quickSort(array, len);
    print(array, len);
}


void quickSort(int array[], int n)
{
    quickSort0(array, 0, n - 1);
}

void quickSort0(int array[], int low, int high)
{
    if (low < high)
    {
        int pivotPos = partition(array, low, high);
        quickSort0(array, low, pivotPos - 1);
        quickSort0(array, pivotPos + 1, high);
    }
}

int partition(int array[], int low, int high)
{
    int pivot = array[low];
    while (low < high)
    {
        while (low < high && array[high] >= pivot)
            high--;
        array[low] = array[high];
        while (low < high && array[low] <= pivot)
            low++;
        array[high] = array[low];
    }
    array[low] = pivot;
    return low;
}